Introduction
Strassen in 1969 which gives an overview that how we can find the
multiplication of two 2*2 dimension matrix by the brute-force
algorithm. But by using divide and conquer technique the overall
complexity for multiplication two matrices is reduced. This happens by
decreasing the total number if multiplication performed at the
expenses of a slight increase in the number of addition.
For multiplying the two 2*2 dimension matrices Strassen's used some
formulas in which there are seven multiplication and eighteen
addition, subtraction, and in brute force algorithm, there is eight
multiplication and four addition. The utility of Strassen's formula is
shown by its asymptotic superiority when order n of matrix reaches
infinity. Let us consider two matrices A and B, n*n dimension, where n
is a power of two. It can be observed that we can contain four n/2*n/2
submatrices from A, B and their product C. C is the resultant matrix
of A and B.
Procedure of Strassen matrix multiplication
There are some procedures:
1. Divide a matrix of order of 2*2 recursively till we get the matrix
of 2*2.
2. Use the previous set of formulas to carry out 2*2 matrix
multiplication.
3. In this eight multiplication and four additions, subtraction are
performed.
4. Combine the result of two matrixes to find the final product or
final matrix.
Formulas for Stassen’s matrix multiplication
In Strassen’s matrix multiplication there are seven multiplication and four addition, subtraction in total.
1. D1 = (a11 + a22) (b11 + b22)
2. D2 = (a21 + a22).b11
3. D3 = (b12 – b22).a11
4. D4 = (b21 – b11).a22
5. D5 = (a11 + a12).b22
6. D6 = (a21 – a11) . (b11 + b12)
7. D7 = (a12 – a22) . (b21 + b22)
C11 = d1 + d4 – d5 + d7
C12 = d3 + d5
C21 = d2 + d4
C22 = d1 + d3 – d2 – d6
Algorithm for Strassen’s matrix multiplication
Algorithm Strassen(n, a, b, d)
begin
If n = threshold then compute
C = a * b is a conventional matrix.
Else
Partition a into four sub matrices a11, a12, a21, a22.
Partition b into four sub matrices b11, b12, b21, b22.
Strassen ( n/2, a11 + a22, b11 + b22, d1)
Strassen ( n/2, a21 + a22, b11, d2)
Strassen ( n/2, a11, b12 – b22, d3)
Strassen ( n/2, a22, b21 – b11, d4)
Strassen ( n/2, a11 + a12, b22, d5)
Strassen (n/2, a21 – a11, b11 + b22, d6)
Strassen (n/2, a12 – a22, b21 + b22, d7)
C = d1+d4-d5+d7 d3+d5
d2+d4 d1+d3-d2-d6
end if
return (C)
end.
Code for Strassen matrix multiplication
#include < stdio.h >
int main()
{
int a[2][2],b[2][2],c[2][2],i,j;
int m1,m2,m3,m4,m5,m6,m7;
printf("Enter the 4 elements of first matrix: ");
for(i=0;i< 2;i++)
for(j=0;j< 2;j++)
scanf("%d",&a[i][j]);
printf("Enter the 4 elements of second matrix: ");
for(i=0;i< 2;i++)
for(j=0;j< 2;j++)
scanf("%d",&b[i][j]);
printf("\nThe first matrix is\n");
for(i=0;i< 2;i++)
{
printf("\n");
for(j=0;j< 2;j++)
printf("%d\t",a[i][j]);
}
printf("\nThe second matrix is\n");
for(i=0;i< 2;i++)
{
printf("\n");
for(j=0;j< 2;j++)
printf("%d\t",b[i][j]);
}
m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]);
m2= (a[1][0]+a[1][1])*b[0][0];
m3= a[0][0]*(b[0][1]-b[1][1]);
m4= a[1][1]*(b[1][0]-b[0][0]);
m5= (a[0][0]+a[0][1])*b[1][1];
m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]);
c[0][0]=m1+m4-m5+m7;
c[0][1]=m3+m5;
c[1][0]=m2+m4;
c[1][1]=m1-m2+m3+m6;
printf("\nAfter multiplication using \n");
for(i=0;i< 2;i++)
{
printf("\n");
for(j=0;j< 2;j++)
printf("%d\t",c[i][j]);
}
return 0;
}
Output:
Enter the 4 elements of first matrix:
5 6 1 7
Enter the 4 element of second matrix:
6 2 8 7
The first matrix is
5 6
1 7
The second matrix is
6 2
8 7
After multiplication
78 52
62 51